package 分类.二分;
/*
和吃香蕉一样，运送能力为自变量，天数为因变量
同递减，左右边界确定时要翻一下
最低运载能力，找左边界
 */
public class 在D天内送达包裹的能力 {
    public int shipWithinDays(int[] weights, int days) {
        /*************************/
        //为了减少运算时间
        int left = 0;
        int right = 1;
        for (int w : weights) {
            left = Math.max(left, w);
            right += w;
        }
        //left为货物中最重的那个，right为货物的总重
        /***********************/
     while (left<=right){
         int mid=(left+right)/2;
         if(f(weights,mid)<=days) right=mid-1;
         else left=mid+1;
     }
     return left;
    }

    /**
     * 返回天数
     * @param weights
     * @param x
     * @return
     */
    static int f(int[] weights,int x){
        int res=1;
        int i=0;
        int cap=x;
        while (i<weights.length){
            cap-=weights[i];
            if(cap<0){
                cap=x;
                res++;
            }else {
                i++;
            }
        }
        return res;
    }


    public static void main(String[] args) {
        int [] arr={3,2,2,4,1,4};
        System.out.println(f(arr,6));
    }
}
